package Solutions

import "sort"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthLargestLevelSum(root *TreeNode, k int) int64 {
	var sum = make([]int64, 0, 16)
	dfs___(root, 0, &sum)
	sort.Slice(sum, func(i, j int) bool {
		return sum[i] < sum[j]
	})
	if len(sum)-k < 0 {
		return -1
	}
	return sum[len(sum)-k]
}

func dfs___(root *TreeNode, depth int, sum *[]int64) {
	if root == nil {
		return
	}
	if depth >= len(*sum) {
		*sum = append(*sum, int64(root.Val))
	} else {
		(*sum)[depth] += int64(root.Val)
	}
	dfs___(root.Left, depth+1, sum)
	dfs___(root.Right, depth+1, sum)
}
